import java.util.Map;
import java.util.TreeMap;

/**
 * 352. 将数据流变为多个不相交区间
 * https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/
 */
public class Solutions_352 {
    public static void main(String[] args) {
        SummaryRanges obj = new SummaryRanges();
        obj.addNum(1);
        int[][] res1 = obj.getIntervals();  // {{1, 1}}

        obj.addNum(3);
        int[][] res2 = obj.getIntervals();  // {{1, 1}, {3, 3}}

        obj.addNum(7);
        int[][] res3 = obj.getIntervals();  // {{1, 1}, {3, 3}, {7, 7}}

        obj.addNum(2);
        int[][] res4 = obj.getIntervals();  // {{1, 3}, {7, 7}}

        obj.addNum(6);
        int[][] res5 = obj.getIntervals();  // {{1, 3}, {6, 7}}
    }
}

class SummaryRanges {
    TreeMap<Integer, Integer> treeMap = null;

    /** Initialize your data structure here. */
    public SummaryRanges() {
        treeMap = new TreeMap<>();
    }

    /**
     * 添加区间，若有相邻区间，则进行合并
     */
    public void addNum(int val) {
        int left = val, right = val;

        // [1, 1] 与 [2, 2] 合并，left 与 right 成为 [1, 2]
        Map.Entry<Integer, Integer> entry = treeMap.floorEntry(val);
        if (entry != null && entry.getValue() + 1 >= val) {
            int key = entry.getKey(), value = entry.getValue();
            // 合并区间
            left = Math.min(left, key);
            right = Math.max(right, value);
            treeMap.remove(key);
        }

        // [2, 2] 与 [3, 3] 合并，left 与 right 成为 [1, 3]
        Map.Entry<Integer, Integer> entry1 = treeMap.ceilingEntry(val);
        if (entry1 != null && entry1.getKey() - 1 <= val) {
            int key = entry1.getKey(), value = entry1.getValue();
            // 合并区间
            left = Math.min(left, key);
            right = Math.max(right, value);
            treeMap.remove(key);
        }
        treeMap.put(left, right);
    }

    /**
     * 获取全部的区间
     */
    public int[][] getIntervals() {
        int[][] res = new int[treeMap.size()][2];
        int idx = 0;
        for (Map.Entry<Integer, Integer> obj : treeMap.entrySet()) {
            res[idx][0] = obj.getKey();
            res[idx][1] = obj.getValue();
            idx ++;
        }
        return res;
    }
}
